﻿// 606 [CF 1516D] cut.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <memory.h>

using namespace std;
/*
http://oj.daimayuan.top/course/22/problem/982

给你一个长度为 n
 的序列 a1,a2,...,an
，以及 q
 次询问。

每次询问给定一个区间 [l,r]
， 我们要把 al,al+1,…,ar
 划分成若干段，要求每一段中数字的 LCM（最小公倍数）等于这一段中数字的乘积。

对于每次询问，求出区间最少可以被划分成几段。

输入格式
第一行两个整数 n,q
，表示序列长度和询问数。

第二行 n
 个整数表示 a1,a2,...,an
。

接下来 q行，每行两个整数 l,r代表一次询问。

输出格式
对于每个询问，输出一行一个整数表示答案。

样例输入
6 3
2 3 10 7 5 14
1 6
2 4
3 5
样例输出
3
1
2
数据规模
对于 100%的数据，保证 1≤n,q≤105,1≤ai≤105,1≤l≤r≤n。
*/

int n, q, a[100001],f[100001][21],v[100001];
vector<int> c[100001];
bool b[100001];








int main()
{
	memset(b, false, sizeof b);
	for (int i = 2; i <= 100000; i++) {
		if (!b[i]) {
			c[i].push_back(i);
			for (int j = i + i; j <= 100000; j += i) {
				b[j] = true;
				c[j].push_back(i);
			}
		}
	}
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++)
		scanf("%d",&a[i]);
	f[n + 1][0] = n + 1;
	memset(v, 127, sizeof v);
	for (int i = n; i; --i) {
		f[i][0] = f[i + 1][0];
		for (auto j : c[a[i]]) {
			f[i][0] = min(f[i][0], v[j]);
			v[j] = i;
		}
	}

	for (int i = 1; i <= 20; i++) {
		for (int j = 1; j <= n; j++) {
			if (f[j][i - 1] <= n)
				f[j][i] = f[f[j][i - 1]][i - 1];
			else
				f[j][i] = n + 1;
		}
	}

	for (; q--;) {
		int l, r;
		scanf("%d%d",&l,&r);
		int ans = 0;
		for(int i= 20;i>=0;--i)
			if (f[l][i] <= r) {
				ans += (1 << i);
				l = f[l][i];
			}
		++ans;
		printf("%d\n", ans);
	}



	return 0;
}

 